'lintcode 滑动拼图2'

Posted on | In

描述

在一个3x3的网格中，放着编号1到8的8块板，以及一块编号为0的空格。
一次移动可以把空格0与上下左右四邻接之一的板子交换。
给定初始和目标的板子排布，返回到目标排布最少的移动次数。
如果不能从初始排布移动到目标排布，返回-1.

样例

初始排布:

[
[2,8,3],
[1,0,4],
[7,6,5]
]
目标排布:

[
[1,2,3],
[8,0,4],
[7,6,5]
]
返回 4
解释:

[ [
[2,8,3], [2,0,3],
[1,0,4], –> [1,8,4],
[7,6,5] [7,6,5]
] ]

[ [
[2,0,3], [0,2,3],
[1,8,4], –> [1,8,4],
[7,6,5] [7,6,5]
] ]

[ [
[0,2,3], [1,2,3],
[1,8,4], –> [0,8,4],
[7,6,5] [7,6,5]
] ]

[ [
[1,2,3], [1,2,3],
[0,8,4], –> [8,0,4],
[7,6,5] [7,6,5]
] ]

思路

和滑动拼图1的思路一样，只需要修改一些参数即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public:
    /**
     * @param init_state: the initial state of chessboard
     * @param final_state: the final state of chessboard
     * @return: return an integer, denote the number of minimum moving
     */
    string vector2string(vector<vector<int>> v) {
        string res(9, '0');
        int j = 0;
        for (int i = 0; i < 3; i++) {
		    for (int k = 0; k < 3; k++) {
			    res[j] = v[i][k] + '0';
			    j++;
		    }
	    }
	    return res;
    }

    vector<vector<int>> string2vector(string tar){
        vector<vector<int>> v(3, vector<int>(3,0));
	    int j = 0;
	    for (int i = 0; i < 3; i++) {
		    for (int k = 0; k < 3; k++) {
			    v[i][k] = tar[j] - '0';
			    j++;
		    }
	    }
	    return v;
    }
    int minMoveStep(vector<vector<int>> &init_state, vector<vector<int>> &final_state) {
        // # write your code here
        string target = vector2string(final_state) , cur = vector2string(init_state);
        vector<vector<int>> move = {{1,0},{0,1},{0,-1},{-1,0}};
        unordered_set<string> s;
        s.insert(cur);
        queue<string> q;
        q.push(cur);
        int res = 0;
        while (!q.empty()) {
            res++;
            int n = q.size();
            while (n > 0) {
                string temp = q.front();
                q.pop();
                if (temp == target)
                    return res-1;
                vector<vector<int>> v = string2vector(temp);
                int pos_x, pos_y;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (v[i][j] == 0) {
                            pos_x = i;
                            pos_y = j;
                            break;
                        }
                    }
                }
                for (int i = 0; i < 4; i++){
                    int new_pos_x = pos_x + move[i][0],
                        new_pos_y = pos_y + move[i][1];
                    if (new_pos_x >= 0 && new_pos_x <=2 && new_pos_y >= 0 && new_pos_y <= 2) {
                        vector<vector<int>> new_v = v;
                        swap(new_v[pos_x][pos_y], new_v[new_pos_x][new_pos_y]);
                        string str = vector2string(new_v);
                        if (s.find(str) == s.end()) {
                            q.push(str);
                            s.insert(str);
                        }
                    }
                }
                n--;

            }
        }
        return -1;
    }
};
-------------end of filethanks for reading-------------